//二叉树
#ifndef __BINARYTREE__HPP
#define __BINARYTREE__HPP

#include"../Universal.h"

namespace NgSiuKei {

//二叉树节点
template<class TheClass>
struct binary_tree_node {
    TheClass val;
    binary_tree_node<TheClass> *parent;
    binary_tree_node<TheClass> *leftChild;
    binary_tree_node<TheClass> *rightChild;
    BinaryTreeNodeColor color;
};

//构造
template<class TheClass>
binary_tree_node<TheClass> *createTree(const TheClass val, binary_tree_node<TheClass> *leftChild, binary_tree_node<TheClass> *rightChild) {
    binary_tree_node<TheClass> *tree = new binary_tree_node<TheClass>;
    tree->val = val;
    tree->parent = nullptr;
    tree->leftChild = leftChild;
    tree->rightChild = rightChild;
    tree->color = BinaryTreeNodeColorRed;
    return tree;
}

//清空
template<class TheClass>
void clearTree(binary_tree_node<TheClass> *&tree) {
    if(nullptr == tree) {
        return;
    }
    clearTree(tree->leftChild);
    clearTree(tree->rightChild);
    delete tree;
}

//插入左孩子树
template<class TheClass>
bool insertLeftSubTree(binary_tree_node<TheClass> * const tree, binary_tree_node<TheClass> * const subTree) {
    if(nullptr != tree->leftChild) {
        return false;
    }
    tree->leftChild = subTree;
    return true;
}

//插入右孩子树
template<class TheClass>
bool insertRightSubTree(binary_tree_node<TheClass> * const tree, binary_tree_node<TheClass> * const subTree) {
    if(nullptr != tree->rightChild) {
        return false;
    }
    tree->rightChild = subTree;
    return true;
}

//拷贝树
template<class TheClass>
binary_tree_node<TheClass> *copyTree(binary_tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        return nullptr;
    }
    binary_tree_node<TheClass> *newTree = new binary_tree_node<TheClass>;
    newTree->val = tree->val;
    newTree->leftChild = copyTree(tree->leftChild);
    newTree->rightChild = copyTree(tree->rightChild);
    return newTree;
}

//获取高度
template<class TheClass>
U_L_L getTreeHeight(const binary_tree_node<TheClass> * const tree) {
    if(nullptr == tree) {
        return 0;
    }
    U_L_L leftHeight = getTreeHeight(tree->leftChild);
    U_L_L rightHeight = getTreeHeight(tree->rightChild);
    return 1+((leftHeight<rightHeight)?(rightHeight):(leftHeight));
}

//获取节点数量
template<class TheClass>
U_L_L getTreeNodeNum(const binary_tree_node<TheClass> * const tree) {
    if(nullptr == tree) {
        return 0;
    }
    return 1+getTreeNodeNum(tree->leftChild)+getTreeNodeNum(tree->rightChild);
}

//先序遍历
template<class TheClass>
static void preOrderTreeToArray(binary_tree_node<TheClass> * const tree, TheClass *&array, U_L_L &index) {
    if(nullptr == tree) {
        --index;
        return;
    }
    // cout << "[wsq-test] index = " << index << endl;
    array[index] = tree->val;
    preOrderTreeToArray(tree->leftChild, array, ++index);
    preOrderTreeToArray(tree->rightChild, array, ++index);
}

//中序遍历
template<class TheClass>
static void inOrderTreeToArray(binary_tree_node<TheClass> * const tree, TheClass *&array, U_L_L &index) {
    if(nullptr == tree) {
        --index;
        return;
    }
    inOrderTreeToArray(tree->leftChild, array, index);
    array[++index] = tree->val;
    inOrderTreeToArray(tree->rightChild, array, ++index);
}

//后序遍历
template<class TheClass>
static void postOrderTreeToArray(binary_tree_node<TheClass> * const tree, TheClass *&array, U_L_L &index) {
    if(nullptr == tree) {
        --index;
        return;
    }
    postOrderTreeToArray(tree->leftChild, array, index);
    postOrderTreeToArray(tree->rightChild, array, ++index);
    array[++index] = tree->val;
}

//层序遍历
template<class TheClass>
static TheClass *levelOrderTreeToArray(binary_tree_node<TheClass> * const tree, TheClass *&array) {
    if(nullptr == tree) {
        return nullptr;
    }
    
    const U_L_L nodeNum = getTreeNodeNum(tree);
    binary_tree_node<TheClass> *arrayNode[nodeNum] = {nullptr};  
    U_L_L in=0, out=0;
    arrayNode[in++] = tree;
    while(in > out) {
        array[out] = arrayNode[out]->val;
        if(in < nodeNum) {
            if(nullptr != arrayNode[out]->leftChild) {
                arrayNode[in++] = arrayNode[out]->leftChild;
            }
            if(nullptr != arrayNode[out]->rightChild) {
                arrayNode[in++] = arrayNode[out]->rightChild;
            }
        }
        out++;
    }
    return array;
}

//遍历
template<class TheClass>
TheClass *orderTree(binary_tree_node<TheClass> * const tree, const BINARY_TREE_ORDER_TYPE type) {
    if(nullptr == tree) {
        return nullptr;
    }

    const U_L_L nodeNum = getTreeNodeNum(tree);
    TheClass *result = new TheClass[nodeNum];
    U_L_L index = 0;

    switch(type) {
        case ORDER_TYPE_PRE: { //前序
            preOrderTreeToArray(tree, result, index);
            break;
        }
        case ORDER_TYPE_IN: { //中序
            inOrderTreeToArray(tree, result, index);
            break;
        }
        case ORDER_TYPE_POST: { //后序
            postOrderTreeToArray(tree, result, index);
            break;
        }
        case ORDER_TYPE_LEVEL: { //层序遍历
            levelOrderTreeToArray(tree, result);
            break;
        }
    }

    return result;
}

//左旋
template<class TheClass>
void leftRotation(binary_tree_node<TheClass> *&tree) {
    if(nullptr == tree || nullptr == tree->rightChild) {
        return;
    }
    binary_tree_node<TheClass> *mainNode = tree;
    binary_tree_node<TheClass> *rightNode = tree->rightChild;

    mainNode->rightChild = rightNode->leftChild;
    rightNode->leftChild = mainNode;
    tree = rightNode;
}

//右旋
template<class TheClass>
void rightRotation(binary_tree_node<TheClass> *&tree) {
    if(nullptr == tree || nullptr == tree->leftChild) {
        return;
    }
    binary_tree_node<TheClass> *mainNode = tree;
    binary_tree_node<TheClass> *leftNode = tree->leftChild;

    mainNode->leftChild = leftNode->rightChild;
    leftNode->rightChild = mainNode;
    tree = leftNode;
}

}

#endif